package Alibaba;

/**
 * @author zhangmin
 * @create 2022-01-18 20:56
 * 剑指 Offer 10- I. 斐波那契数列
 * 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。F(0) = 0,   F(1) = 1,F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
 * dp,答案需要取模 1e9+7（1000000007）
 */
public class fib {
    public int fib(int n) {
        if (n<=1) return n;
        int mod=1000000007;
        int f_1=0,f_2=1;
        for (int i = 2; i <= n; i++) {
            int f=(f_1+f_2)%mod;
            f_1=f_2;
            f_2=f;
        }
        return f_2;
    }
}
